<!DOCTYPE html>
<html lang="zh-cn">
<head>
    <title>线性方程组</title>
    <meta charset="utf-8" />
    <link rel="stylesheet" type="text/css" href="../../css/note.css" />
</head>
<body>

<h2>预备知识</h2>
<h2>直接法：Gauss 消去、矩阵分解</h2>
<h2>迭代法：Jacobi、Gauss-Seidel、SOR</h2>
<h2>共轭梯度法</h2>

<p>	<b>共轭梯度法 (conjugate gradient method)</b>
	最早由德国的 Hestenes 和 Stiefel 于 1952 年提出,
	适用于系数矩阵对称正定的情形, 收敛速度较上一节的三种迭代法更快.
	它的思想基于数学物理中的<b>变分原理</b>.
</p>

<p>	熟知二次函数 `1/2 ax^2 - bx` 在 `x = b/a` 处取得极小值.
	将这一结果推广至 `n` 元函数, 有:
</p>

<p class="theorem">
	设 `bm A` 为对称正定矩阵. 则方程组 `bm (Ax) = bm b` 的求解等价于求
	二次泛函 (二次型)
	<span class="formula">
		`varphi(bm x) = 1/2 (bm (Ax), bm x) - (bm b, bm x)`
	</span>
	在 `RR^n` 上的极小值.
</p>

<p class="proof">
	设 `bm x_0` 是方程组 `bm (Ax) = bm b` 的解, 则有
	<span class="formula">
		` varphi(bm x_0) = 1/2 (bm (Ax_0), bm x_0) - (bm b, bm x_0)
		= -1/2 (bm (Ax_0), bm x_0)`.
	</span>
	对 `AA bm x in RR^n`,
	<span class="formula">
		` varphi(bm x) - varphi(bm x_0)
		= 1/2 (bm (Ax), bm x) - (bm b, bm x) + 1/2 (bm (Ax_0), bm x_0)`
		`= 1/2 [(bm (Ax, bm x))-2(bm (Ax_0, bm x)) + (bm (Ax_0), bm x_0)]`
		`= 1/2 (bm (A(x - x_0)), bm (x-x_0))
		= 1/2 ||bm x - bm x_0||_(bm A)^2 ge 0`.
	</span>
	由 `bm A` 的正定性知, `bm x_0` 为 `varphi(bm x)` 的唯一极小值点.
</p>

<script src="../../js/note.js?type=math"></script>
</body>
</html>
